package leetcode_1000;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 *@author 周杨
 *MostStonesRemovedWithSameRowOrColumn_947 二维平面上给定N个坐标 如果有两个点在同一个轴上 可以一次消除一个 问消除的最大次数
 *describe:用广度优先遍历
 *2018年11月25日 下午7:53:27
 */
public class MostStonesRemovedWithSameRowOrColumn_947 {
	public static void main(String[] args) {
		MostStonesRemovedWithSameRowOrColumn_947 test=new MostStonesRemovedWithSameRowOrColumn_947();
		System.out.println(test.removeStones(new int[][] {{0,0},{0,1},{1,0},{1,2},{2,1},{2,2}}));
	}
	
	public int removeStones(int[][] stones) {
        Map<Integer,List<Integer>> map=new HashMap<Integer,List<Integer>>();
        for(int i=0;i<stones.length;++i) {
        	for(int j=i+1;j<stones.length;++j) {
        		if(stones[i][0]==stones[j][0]||stones[i][1]==stones[j][1]) {
        			List<Integer> listi=map.get(i);
        			List<Integer> listj=map.get(j);
        			if(listi==null) listi=new ArrayList<Integer>();
        			if(listj==null) listj=new ArrayList<Integer>();
        			listi.add(j);
        			listj.add(i);
        			map.put(i, listi);
        			map.put(j, listj);
        		}
        	}
        }
        boolean []visited=new boolean[stones.length];
        int res=0;
        for(int i=0;i<stones.length;++i) {
        	if(!visited[i]) {
	        	Queue<Integer> queue=new LinkedList<Integer>();
	        	visited[i]=true;
	        	queue.offer(i);
	        	--res;
	        	while(!queue.isEmpty()) {
	        		int node=queue.poll();
	        		++res;
	        		List<Integer> now=map.get(node);
	        		if(now!=null) {
	        			for(int next:now) {
	        				if(!visited[next]) {
	        					queue.offer(next);
	        					visited[next]=true;
	        				}
	        			}
	        		}
	        	}      		
        	}
        }
        return res;
    }
}
